package LeetCode.SegmentTree;

/**
 * @author : LdLtd
 * @Date : 2023/11/13
 * @Description:线段树
 */
public class SegmentTree {
    static int [] sum;
    static  int [] a;
    //根据tag的定义，tag可以是把区间内都变为一个数，也可以一个区间都加上一个数
    static int [] tag;
    static int []  min;
    public static void main(String[] args) {
        sum = new int[20];
        a = new int[]{1, 3,5,7,9,11};
        tag=new int[20];
        min=new int[20];
        build(0, a.length-1, 0);
        System.out.println(query(2, 3, 0, a.length-1, 0));
        change(2, 10, 0, 9, 0);
        System.out.println(query(2, 3, 0, a.length-1, 0));
    }

    public static void update(int x){
       sum[x]=sum[x*2]+sum[x*2+1];
        //求区间最小值，维护min数组
        min[x]=Math.min(min[x*2],min[x*2+1] );
    }

    public static void build(int l,int r,int x){
        //叶子节点
        if(l==r){
            sum[x]=a[l];
            min[x]=a[l];
            return;
        }
        int m=(l+r)>>1;
        build(l,m,x*2);
        build(m+1,r,x*2+1);
        update(x);
    }
    /*查询区间a,b
    * 左区间为l,m，右区间为m+1,r
    * 如果a<=m，即询问区间与左子节点有重合，需要递归到左子节点
    * 如果b>=m+1,即询问区间与右子节点有重合，需要递归到右子节点
    * 递归完的结果加上*/
    public static int query(int a,int b,int l,int r,int x){
        if(a<=l&&r<=b){
         //   return sum[x];
            return min[x];
        }
        //继续查询前，先检查是否下传标记
        down(l,r,x);
        int m=(l+r)>>1;
        //求和时
        //int res=0;
        //查询区间最小时
        int res=Integer.MAX_VALUE;
        if(a<=m){
            //求和
           // res+=query(a,b,l,m,x*2);
            //求最小值
            res=Math.min(res,query(a,b,l,m,x*2));
        }
        if(m<b){
            //求和
           // res+=query(a,b,m+1,r,x*2+1);
            //求最小值
            res=Math.min(res,query(a,b,m+1,r,x*2+1));
        }
        return  res;
    }
    /*把pos位置的改成值为v，x是启动节点，l,r是启动节点区间*/
    public  static void change(int pos,int v,int l,int r,int x){
        if (l==r) {
            sum[x]=v;
            min[x]=v;
            return ;
        }
        int m=(l+r)>>1;
        //pos在左子节点
        if(pos<=m){
            change(pos,v,l,m,x*2);
        }else {
            change(pos,v,m+1,r,x*2+1);
        }
        update(x);
    }
    /*修改区间，把a,b区间修改为v*/
    public  static void change(int a,int b,int v,int l,int r,int x){
        if (a<=l&&r<=b) {
            //这里tag是变成v
            //tag[x]=v;
            //sum[x]=v*(r-l+1);
            //这里tag是区间加上v
            tag[x]+=v;
            sum[x]+=v*(r-l+1);
            min[x]+=v;
            return;
        }
        //修改前，先检查是否要下传
       down(l,r,x);
        int m=(l+r)>>1;
        if(a<=m) change(a,b,v,l,m,x*2);
        if(m<b) change(a,b,v,m+1,r,x*2+1);
        //回溯时更新每个节点的sum
        update(x);
    }

    /*下传函数*/
    public  static void down(int l,int r,int x){
        int m=(l+r)>>1;
        //这里的tag定义是区间变成一个数
//        if(tag[x]>0){
//            //左右孩子的tag标记
//            tag[x*2]=tag[x*2+1]=tag[x];
//            //左边区间和右边区间
//            sum[x*2]=(m-l+1)*tag[x];
//            sum[x*2+1]=(r-m)*tag[x];
//            tag[x]=0;
//        }
        //这里的tag定义是区间加上一个数
        if(tag[x]!=0){
            //左右孩子的tag标记
            tag[x*2]+=tag[x];
            tag[x*2+1]+=tag[x];
            //左边区间和右边区间
            sum[x*2]+=(m-l+1)*tag[x];
            sum[x*2+1]+=(r-m)*tag[x];

            //维护最小值
            min[x*2]+=tag[x];
           min[x*2+1]+=tag[x];
            tag[x]=0;
        }
    }

}
